package 链表.删除链表的倒数第N个结点_19;

public class Solution {

static  ListNode[] head = new ListNode[4];
    public static void main(String[] args) {
        head[3] = new ListNode(4,null);
        head[2] = new ListNode(3,head[3]);
        head[1] = new ListNode(2,head[2]);
        head[0] = new ListNode(1,head[1]);
        ListNode answer = removeNthFromEnd(head[2], 1);
        int sum = 0;
        while (answer != null){
            System.out.println(answer.val);
            answer = answer.next;
        }
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {

        if(head == null || head.next == null){
            return null;
        }

        ListNode pre = reverse(head); // 将原链表翻转
        ListNode dumyhead = new ListNode(-1, pre); //虚拟头节点
        ListNode temp = dumyhead;
        for (int i = 1; i < n; i ++){
            temp = temp.next; // 找到前一个节点
        }
        temp.next = temp.next.next; // 将第n个节点删除

        return reverse(dumyhead.next); // 将链表重新翻转回来
    }

    static ListNode reverse(ListNode head){
        ListNode pre = null; // 前一个节点
        ListNode cur = head; // 当前需要改变的节点
        ListNode temp = null;  // 下一个节点

        while (cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    // 方法2，双指针法，前后快慢指针间隔n即可 无虚拟头结点法，需要讨论前后，如果是虚拟头节点可以不用讨论
    public static ListNode removeNthFromEnd_2(ListNode head, int n) {
        ListNode slow = head;
        ListNode fast = head;
        for (int i = 0; i < n; i ++){
            if (fast == null){ // 如果n>链表长度返回null
                return null;
            }
            fast = fast.next; // fast到间隔n的链表位置去
        }
        if (fast == null){  // 如果n正好是链表长度，则要把慢指针删掉，此时慢指针只能在原地，因为二者间隔n，fast还过界 例如[1,2] 2的情况
            return head.next;
        }
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        if (n == 1){ // 当slow的下一个节点是空，即将fast节点删掉，那么直接移动一个就行，其他情况就是slow一直移动，否则的话 slow.next为空没有next
            slow.next = null;
        } else {
            slow.next = slow.next.next;
        }
        return head;
    }

    public static class ListNode {
        public int val;
        public ListNode next;
        public ListNode() {}
        public ListNode(int val) { this.val = val; }
        public ListNode(int val, ListNode next) { this.val = val; this.next = next;
        }
    }
}
